import java.util.HashMap;
import java.util.Map;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/8/2 9:51
 */
// 随机链表的复制
    // 对于数据结构的复制：一次哈希表+两次遍历
    // https://leetcode.cn/problems/copy-list-with-random-pointer/
    // 1，拷贝所有的节点，然后进行连接起来，每个拷的的结点连接到后面。这样方便处理下一步的random
    // 2，处理random节点
    // 3，处理复制出来的结点与原来链表的关系，返回头结点
public class Solution138 {
    public Node copyRandomList(Node head) {
        Map<Node, Node> originToClone = new HashMap<Node, Node>();
        // 第一次遍历复制节点
        for (Node p = head; p != null; p = p.next) {
            if (!originToClone.containsKey(p)) {
                originToClone.put(p, new Node(p.val));
            }
        }
        // 第二次遍历，构造结构
        for (Node p = head; p != null; p = p.next) {
            if (p.next != null) {
                originToClone.get(p).next = originToClone.get(p.next);
            }
            if (p.random != null) {
                originToClone.get(p).random = originToClone.get(p.random);
            }
        }
        return originToClone.get(head);
    }
}
